
from queue import PriorityQueue
from public import *
import time
def a_star(maze,canvas,start,end,step_x,step_y):
    size_y=len(maze)
    size_x=len(maze[0])
    dis=[[255 for i in range(size_x)]for j in range(size_y)]
    record=[[None for i in range(size_x)]for j in range(size_y)]

    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    queue=PriorityQueue()
    queue.put((0,start))
    dis[start.y][start.x]=0

    while not queue.empty():
        find=False
        head=queue.get()#得到最小的
        cur=head[1]
        canvas.create_rectangle(cur.x*step_x,cur.y*step_y,(cur.x+1)*step_x,(cur.y+1)*step_y,fill="purple",outline="black")
        canvas.update()
        for i in range(4):
            smell_x,smell_y=cur.x+dx[i],cur.y+dy[i]
            if 0<=smell_x<size_x and 0<=smell_y<size_y and maze[smell_y][smell_x]!=1:
                temp_value=dis[cur.y][cur.x]+1
                if temp_value<dis[smell_y][smell_x]:
                    dis[smell_y][smell_x]=temp_value
                    # print("record:%d==%d" %(cur.y,cur.x))
                    record[smell_y][smell_x]=cur
                    # 当前代价+预估代价
                    priority=dis[smell_y][smell_x]+abs(smell_x-end.x)+abs(smell_y-end.y)
                    queue.put((priority,pos(smell_x,smell_y)))
                    canvas.create_rectangle(smell_x*step_x,smell_y*step_y,(smell_x+1)*step_x,(smell_y+1)*step_y,fill="green",outline="black")
                    canvas.update()
                    time.sleep(0.1)

                    if smell_x==end.x and smell_y==end.y:
                        find=True
                        break
        if find==True:
            stack=[]#定义一个栈
            cur=end
            stack.append(cur)
            while cur.x!=start.x or cur.y!=start.y:
                cur=record[cur.y][cur.x]
                # print("pop:%d==%d" %(cur.y,cur.x))
                stack.append(cur)
            while stack:
                cur=stack.pop()
                # print("stack:%d==%d" %(cur.y,cur.x))
                canvas.create_rectangle(cur.x*step_x,cur.y*step_y,(cur.x+1)*step_x,(cur.y+1)*step_y,fill="red",outline="black")
                canvas.pack()
            return True
    return False          

